package com.github.yangyishe.p300;

/**
 * 201. 数字范围按位与
 * https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：left = 5, right = 7
 * 输出：4
 * 示例 2：
 *
 * 输入：left = 0, right = 0
 * 输出：0
 * 示例 3：
 *
 * 输入：left = 1, right = 2147483647
 * 输出：0
 *
 *
 * 提示：
 *
 * 0 <= left <= right <= 231 - 1
 */
public class Problem201 {
    public static void main(String[] args) {
        int left=5;
        int right=7;

        Problem201 problem201 = new Problem201();
        int i = problem201.rangeBitwiseAnd(left, right);
        System.out.println("i = " + i);

    }

    /**
     * 思路:
     * 某一个bit为1的条件, 比如该位所代表的二进制数为n.
     * 则:
     * 1. left le n // 如果不满足, 则left就通过按位与将该值排除掉了
     * 2. n<<1 ge right // 如果不满足, 虽然通过left使该数参与竞争, 但right gt n<<2 的情况, 必定出现值为0的bit
     *
     *
     *
     * @param left
     * @param right
     * @return
     */
    public int rangeBitwiseAnd(int left, int right) {
        int result=0;
        for(int i=31;i>=0;i--){
            int comp=1<<i;
            boolean compSame = (comp & left) == (comp & right);
            if(compSame){
                if((comp & left)!=0){
                    result|=comp;
                }

            }else{
                break;
            }
        }

        return result;
    }
}
